#define BinNodePosi(T) BinNode<T> *
#define stature(p) ((p) ? (p)->height : -1)

#define IsRoot(x) (!((x).parent))
#define IsLChild(x) (!IsRoot(x) && (&(x) == (x).parent->lc))
#define IsRChild(x) (!IsRoot(x) && (&(x) == (x).parent->rc))
#define HasParent(x) (!IsRoot(x))
#define HasLChild(x) ((x).lc)
#define HasRChild(x) ((x).rc)
#define HasChild(x) (HasLChild(x) || HasRChild(x))
#define HasBothChild(x) (HasLChild(x) && HasRChild(x))
#define IsLeaf(x) (!HasChild(x))

template <typename T>
struct BinNode
{
    T data;
    BinNodePosi(T) parent, lc, rc;

    int height;

    BinNode() : parent(NULL), lc(NULL), rc(NULL), height(0) {}
    BinNode(T e, BinNodePosi(T) p = NULL, BinNodePosi(T) lc = NULL,
            BinNodePosi(T) rc = NULL, int h = 0)
        : data(e), parent(p), lc(lc), rc(rc), height(h) {}

    BinNodePosi(T) succ(); // 取当前节点的直接后继

    bool operator<(BinNode const &bn) { return data < bn.data }
    bool operator==(BinNode const &bn) { return data == bn.data }
};

template <typename T>
BinNodePosi(T) BinNode<T>::succ()
{                            //定位节点v的直接后继
    BinNodePosi(T) s = this; //记录后继的临时变量
    if (rc)
    {           //若有右孩子，则直接后继必在右子树中，具体地就是
        s = rc; //右子树中
        while (HasLChild(*s))
            s = s->lc; //最靠左（最小）的节点
    }
    else
    { //否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”，具体地就是
        while (IsRChild(*s))
            s = s->parent; //逆向地沿右向分支，不断朝左上方移动
        s = s->parent;     //最后再朝右上方移动一步，即抵达直接后继（如果存在）
    }
    return s;
}
